package org.example.Soution003;

import java.util.Arrays;

public class DynamicProgrammingArrayDivide {
    public static void main(String[] args) {
        DynamicProgrammingArrayDivide dp = new DynamicProgrammingArrayDivide();
        int[] nums=new int[]{1,2,3,5} ;
        System.out.println(dp.canPartition(nums));
    }


    public boolean canPartition(int[] nums) {
        int n=nums.length;
        if(n<2) return false;
        int sum=0;int maxNum=0;
        for(int num:nums){
            sum+=num;
            maxNum=Math.max(maxNum,num);
        }
        if(sum%2!=0) return false;
        int target=sum/2;
        if(target<maxNum) return false;
        boolean[] helper=new boolean[target+1];
        helper[0]=true;
        for(int num:nums){
            for(int i=target;i>=num;i--){
                if(helper[i-num]) helper[i]=true;
                if(helper[target]){
//                    System.out.println(Arrays.toString(helper));
                    return true;
                }
            }
        }
//        System.out.println(Arrays.toString(helper));
        return helper[target];
    }
}
